public class demo1 {
    class Solution {
        int [][]memo;
        public int uniquePaths(int m, int n) {
            memo=new int[m+1][n+1];
            // 动态规划
            // int [][]arr=new int[m+1][n+1];
            // arr[0][1]=1;
            // for(int i=1;i<=m;i++){
            //     for(int j=1;j<=n;j++){
            //         arr[i][j]=arr[i-1][j]+arr[i][j-1];
            //     }
            // }
            // return arr[m][n];
            return dfs(m,n);
        }
        public int dfs(int m,int n){
            if(m==0||n==0)return 0;
            if(memo[m][n]!=0)return memo[m][n];

            if(m==1&&n==1){
                memo[m][n]=1;
                return 1;
            }
            memo[m][n]=dfs(m-1,n)+dfs(m,n-1);
            return memo[m][n];
        }
    }
}
